#include <iostream>
#include <vector>
#include <map>
using namespace std;

#if 1
class Solution 
{
    public:
        vector<int> twoSum(vector<int>& nums, int target) 
        {
            multimap<int, int> hashid;
            for (int i = 0; i < nums.size() ; i++)
            {
                hashid.insert(make_pair(nums[i], i));
            }
            for (int i = 0; i < nums.size(); i++)
            {
                if (target -  nums[i] != nums[i])
                {
                    if (hashid.count(target - nums[i]))
                    {
                        ret.push_back(i);
                        ret.push_back(hashid.lower_bound(target - nums[i])->second);
                        return ret;
                    }
                }
                else
                {
                    if (hashid.count(target - nums[i]) > 1)
                    {
                        multimap<int, int>::iterator p, beg, end;
                        p = hashid.find(target - nums[i]);
                        beg = hashid.equal_range(nums[i]).first;
                        end = hashid.equal_range(nums[i]).second;
                        for ( p = beg; p != end; p++)
                        {
                            ret.push_back(p->second);
                        }
                        return ret;
                    }
                }
            }
        }
        vector<int> ret;
};
#endif
#if 0
// multimap test
int main()
{

    multimap<int, int> mp;
    mp.insert(make_pair(1, 5));
    mp.insert(make_pair(2, 20));
    mp.insert(make_pair(3, 30));
    mp.insert(make_pair(1, 50));
    cout << (mp.lower_bound(1))->second << endl;
    multimap<int, int>::iterator beg, end, m;
    m = mp.find(1);
    beg = mp.equal_range(1).first;
    end = mp.equal_range(1).second;
    for (m = beg; m != end; m++)
        cout << m->second<< endl;
    return 0;
}
#endif


//test alg
int main()
{
    return 0;
}
